package top101K.linkedList;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author quan
 * @Description 删除重复链表，不留
 * @Date 2023/8/2 21:07
 */
public class Demo16_DeleteDuplicates {
    /**
     * 删除链表中的重复元素：不留一个
     * 使用map的去重特性：计数
     * 指针cur从虚拟头结点开始，如果cur的下一个节点的值对应的个数是1，就直接移动该指针cur = cur.next；
     * 否则就将cur.next指向cur.next.next
     * @param head
     * @return
     */
    public ListNode deleteDuplicates (ListNode head) {
        //空链表
        if (head == null)
            return null;
        //创建一个哈希表
        Map<Integer, Integer> map = new HashMap<>();
        ListNode cur = head;
        //遍历链表统计每个节点值出现的次数
        while (cur != null) {
            if (!map.containsKey(cur.val)) {
                //如果该值在map中是第一次出现，就设置个数为1
                map.put(cur.val, 1);
            } else {
                //否则就在原先的基础上加1
                map.put(cur.val, map.get(cur.val) + 1);
            }
            cur = cur.next;
        }
        //创建虚拟头结点
        ListNode dummyHead = new ListNode(0);
        //在链表前加一个表头
        dummyHead.next = head;
        cur = dummyHead;
        //再次遍历链表
        while (cur.next != null) {
            //如果这个节点的个数不为1，就删除该节点
            if (map.get(cur.next.val) != 1) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        //返回头结点
        return dummyHead.next;
    }

    /**
     * 递归做法：如果头结点不是重复的节点，直接将头结点开始的链表进行递归三处；
     * 如果头结点是重复的节点，就要创建一个新的头结点，确保该节点不是重复的节点之后再递归删除
     * @param head
     * @return
     */
    public ListNode deleteDuplicates1 (ListNode head) {
        //base case
        if(head == null || head.next == null){
            return head;
        }
        //如果头结点不是要被删除的节点，就将下一个节点进行递归的删除
        if(head.val!=head.next.val){
            head.next = deleteDuplicates1(head.next);
            return head;
        }else{
            //说明头结点就是重复的节点：先处理头结点的情况
            ListNode newHead = head.next;
            while (newHead!=null && newHead.val == head.val){
                newHead = newHead.next;
            }
            //说明此时的newHead一定不是待删除的节点，递归删除新的不重复的头结点
            return deleteDuplicates(newHead);
        }
    }

    public ListNode deleteDuplicates3(ListNode head) {
//         1.base case
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(-101);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;
        while (cur != null) {
            ListNode sec = cur.next;
            if (sec == null) {
                break;
            }
            if (cur.val != sec.val) {
                prev = prev.next;
            }else {
                // 此时cur和sec相等
                while (sec != null && cur.val == sec.val) {
                    sec = sec.next;
                }
                // 此时sec一定走到第一个和cur不相等的结点
                // prev .. sec全都是待删除的结点
                prev.next = sec;
            }
            cur = sec;
        }
        return dummyHead.next;
    }
}
